#include <iostream>
using namespace std;

struct ElemType
{
    int data;
};

/// @brief 线索二叉树
typedef struct ThreadNode
{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; // 左、右线索标志
} ThreadNode, *ThreadTree;

/// @brief 全局变量pre，指向当前访问节点的前驱
ThreadNode *pre = NULL;

void visit(ThreadNode *q)
{
    if (q->lchild == NULL) // 左子树为空，建立前驱线索
    {
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) // 建立前驱节点的后续线索
    {
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}

/////////////////////////中序线索化二叉树///////////////////////////////////////////////

/// @brief 中序遍历二叉树，一边遍历一边线索化
/// @param T
void InThread(ThreadTree T)
{
    if (T != NULL)
    {
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}

/// @brief 中序线索化二叉树T
/// @param T
void CreateInThread(ThreadTree T)
{
    pre = NULL;    // pre初始为NULL
    if (T != NULL) // 非空二叉树才能线索化
    {
        InThread(T); // 中序线索化二叉树
        if (pre->rchild == NULL)
        {
            pre->rtag = 1; // 处理遍历的最后一个节点
        }
    }
}

////////////////////////先序遍历二叉树////////////////////////////////////////////////

/// @brief 先序遍历二叉树，一边遍历一边线索化
/// @param T
void PreThread(ThreadTree T)
{
    if (T != NULL)
    {
        visit(T); // 先处理根节点
        if (T->ltag == 0)
        { // lchild不是前驱线索
            PreThread(T->lchild);
        }
        PreThread(T->rchild);
    }
}

/// @brief 先序线索二叉树T
/// @param T
void CreatPreThread(ThreadTree T)
{
    pre = NULL;    // pre初始为NULL
    if (T != NULL) // 非空二叉树才能线索化
    {
        PreThread(T); // 先序线索化二叉树
        if (pre->rchild == NULL)
        {
            pre->rtag = 1; // 处理便利的最后一个节点
        }
    }
}

////////////////////////后序遍历二叉树////////////////////////////////////////////////

/// @brief 后序遍历二叉树，一边遍历一边线索化
/// @param T
void PostThread(ThreadTree T)
{
    if (T != NULL)
    {
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}

/// @brief 后续线索化二叉树T
/// @param T
void CreatdPostThread(ThreadTree T)
{
    pre = NULL;
    if (T != NULL)
    {
        PostThread(T);
        if (pre->rchild != NULL)
        {
            pre->rtag = 1;
        }
    }
}

/////////////////////中序线索二叉树找中序后继////////////////////////////////////////////

/// @brief 找到以p为根的子树中，第一个被中序遍历的节点
/// @param p
/// @return
ThreadNode *Firstnode(ThreadNode *p)
{
    // 循环找到最左下节点（不一定叶节点）
    while (p->ltag == 0)
    {
        p = p->lchild;
    }
    return p;
}

/// @brief 在中序线索二叉树中找到节点p的后继节点
/// @param p
/// @return
ThreadNode *Nextnode(ThreadNode *p)
{
    // 右子树最左下节点
    if (p->rtag == 0)
    {
        return Firstnode(p->rchild);
    }
    else
    {
        p->rchild;
    }
}

/// @brief 对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
/// @param T
void Inorder(ThreadNode *T)
{
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
    {
        visit(p);
    }
}

//////////////////////////中序线索二叉树找中序前驱/////////////////////////////////

/// @brief 找到以P为根的子树，最后一个被中序遍历的节点
/// @param p
/// @return
ThreadNode *Lastnode(ThreadNode *p)
{
    // 循环找到最右下节点（不一定是叶节点）
    while (p->rtag == 0)
    {
        p = p->rchild;
    }
    return p;
}

/// @brief 在中序线索二叉树中找到节点p的前驱节点
/// @param p
/// @return
ThreadNode *Prenode(ThreadNode *p)
{
    if (p->ltag == 0)
    {
        return Lastnode(p->lchild);
    }
    else
    {
        return p->lchild; // ltag==1 直接返回前驱线索
    }
}

/// @brief 对中序线索二叉树进行逆向中序遍历
/// @param T
void RevInorder(ThreadNode *T)
{
    for (ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p))
    {
        visit(p);
    }
}

//////////////////////////中序线索二叉树找中序前驱/////////////////////////////////

/// @brief 找到以p为根的子树中，最后一个被中序遍历的节点
/// @param p
/// @return
ThreadNode *InLastnode(ThreadNode *p)
{
    // 循环找到最右下节点（不一定是叶节点）
    while (p->rtag == 0)
    {
        p = p->rchild;
    }
    return p;
}

/// @brief 在中序线索二叉树中找到节点p的前驱节点
/// @param p
/// @return
ThreadNode *InPrenode(ThreadNode *p)
{
    if (p->ltag == 0)
    {
        return InLastnode(p->lchild);
    }
    else
    {
        return p->lchild; // ltag==1直接返回前驱线索
    }
}

/// @brief 对中序线索二叉树进行逆向中序遍历
/// @param T
void InRevInorder(ThreadNode *T)
{
    for (ThreadNode *p = InLastnode(T); p != NULL; p = InPrenode(p))
    {
        visit(p);
    }
}


//////////////////////////先序线索二叉树找先序后继/////////////////////////////////



